﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System;
using Object = UnityEngine.Object;
using System.Linq;

namespace ns
{

    public class ArrayQuestion : MonoBehaviour
    {
        //26. 删除排序数组中的重复项（双指针）
        //https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/	
        public int RemoveDuplicates(int[] nums)
        {
            if (nums.Length == 0) return 0;
            int i = 0; //长度
            for (int j = 1; j < nums.Length; j++)
            {
                if (nums[i] != nums[j])
                {
                    i++;
                    nums[i] = nums[j];
                }
            }
            return i + 1;
        }

        //27. 移除元素（双指针）
        //https://leetcode-cn.com/problems/remove-element/
        public int RemoveElement(int[] nums, int val)
        {
            int i = 0;
            int n = nums.Length;
            while (i < n)
            {
                if (nums[i] == val)
                {
                    nums[i] = nums[n - 1];
                    n--;
                }
                else
                {
                    i++;
                }
            }
            return n;
        }

        //35.搜索插入位置（二分法）
        //https://leetcode-cn.com/problems/search-insert-position/
        public int SearchInsert(int[] nums, int target)
        {
            int left = 0;
            int right = nums.Length - 1;
            int ans = right + 1; //防止超出索引
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (target <= nums[mid])
                {
                    ans = mid;
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            return ans;
        }

        //36 有效的数独
        //https://leetcode-cn.com/problems/valid-sudoku/
        //
        public bool IsValidSudoku(char[][] board)
        {
            //Init Data
            Dictionary<int, int>[] row = new Dictionary<int, int>[9]; //行
            Dictionary<int, int>[] col = new Dictionary<int, int>[9]; //列
            Dictionary<int, int>[] box = new Dictionary<int, int>[9]; //宫
            for (int i = 0; i < 9; i++)
            {
                row[i] = new Dictionary<int, int>();
                col[i] = new Dictionary<int, int>();
                box[i] = new Dictionary<int, int>();
            }

            //Valid board
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    char num = board[i][j];
                    if (num != '.')
                    {
                        int n = (int)num;
                        int box_index = (i / 3) * 3 + j / 3;

                        //check it this the value has been already exists before
                        if (!row[i].ContainsKey(board[i][j]) && !col[j].ContainsKey(board[i][j]) && !box[box_index].ContainsKey(board[i][j]))
                        {
                            //Keep Current Data In Dictionary
                            row[i].Add(board[i][j], i);
                            col[j].Add(board[i][j], j);
                            box[box_index].Add(board[i][j], box_index);
                        }
                        else
                            return false;
                    }
                }
            }
            return true;
        }

        //53.最大子序和（动态规划，贪心）
        //https://leetcode-cn.com/problems/maximum-subarray/
        public int MaxSubArray(int[] nums)
        {
            int pre = 0;
            int maxAns = nums[0];
            foreach (var x in nums)
            {
                pre = Math.Max(pre + x, x); //pre+x ：前面的值+当前值
                maxAns = Math.Max(maxAns, pre);
            }
            return maxAns;
        }

        //66.加一（9进位，999进位1000）
        //https://leetcode-cn.com/problems/plus-one/
        public int[] PlusOne(int[] digits)
        {
            for (int i = digits.Length - 1; i >= 0; i--) //递减
            {
                digits[i]++;
                digits[i] %= 10; //求余 6%10 = 6 ， 0 （9+1）% 10=0，
                if (digits[i] != 0) //等于0就一直循环
                    return digits;
            }
            digits = new int[digits.Length + 1]; //999和99情况
            digits[0] = 1;
            return digits;
        }

        //88.合并两个有序数组（合并后排序，双指针从前往后）
        //https://leetcode-cn.com/problems/merge-sorted-array/
        public void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            for (int i = m; i < m + n; i++)
            {
                nums1[i] = nums2[i - m];
            }
            Array.Sort(nums1);
        }

        //118.杨辉三角（动态规划，取巧：下一行是上一行本身的错位相加13310+01331=14641）
        //https://leetcode-cn.com/problems/pascals-triangle/
        public IList<IList<int>> Generate(int numRows)
        {
            IList<IList<int>> result = new List<IList<int>>();
            if (numRows == 0) return result; //直接输出1
            for (int i = 0; i < numRows; i++) //i代表第几排
            {
                IList<int> newRow = new List<int>(numRows);
                if (i == 0) //第一排一直为0
                {
                    newRow.Add(1);
                    //result.Add(newRow);
                }
                else
                {
                    var list = result[i - 1];
                    for (int j = 0; j < i + 1; j++) //j代表第几列
                    {
                        if (j == 0 || j == i) // 首位和末尾都是1
                        {
                            newRow.Add(1);
                        }
                        else
                        {
                            newRow.Add(list[j - 1] + list[j]);
                        }
                    }
                }
                result.Add(newRow); //赋值列表
            }
            return result;
        }

        //119.杨辉三角2（层层求，公式法，）
        //https://leetcode-cn.com/problems/pascals-triangle-ii/
        public IList<int> GetRow(int rowIndex)
        {
            IList<int> cur = new List<int>();
            cur.Add(1); //第一个1
            for (int i = 1; i < rowIndex; i++) //i=1,从第2行开始
            {
                for (int j = i - 1; j > 0; j--) //防止j覆盖所以从后往前
                {
                    cur[j] = cur[j - 1] + cur[j];
                }
                cur.Add(1); //最后一个1
            }
            return cur;
        }

        //122. 买卖股票的最佳时机 II
        //https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
        //方法一：贪心算法【每一次都是最优解~】
        public int MaxProfit(int[] prices)
        {
            int maxProfit = 0;
            for (int i = 0; i < prices.Length - 1; i++)
            {
                int profit = prices[i + 1] - prices[i];
                if (profit > 0)
                {
                    maxProfit += profit;
                }
            }
            return maxProfit;
        }

        //136.只出现一次的数字
        //https://leetcode-cn.com/problems/single-number/
        //满足线性，异或运算方法，或O(n)复杂度的哈希表
        public int SingleNumber(int[] nums)
        {
            int ret = 0;
            foreach (var item in nums)
            {
                ret ^= item; //A和0异或是A，A和A异或是0，异或满足交换律，A异或B异或A=B
            }
            return ret;
        }

        //167.两数之和2——输入有序数组（二分、指针）
        //https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
        public int[] TwoSum(int[] numbers, int target)
        {
            for (int i = 0; i < numbers.Length; i++)
            {
                int low = i + 1, high = numbers.Length - 1; //下标
                while (low <= high)
                {
                    int mid = (high - low) / 2 + low;
                    if (numbers[mid] == target - numbers[i])
                    {
                        return new int[] { i + 1, mid + 1 };//返回下标
                    }
                    else if (numbers[mid] > target - numbers[i])
                    {
                        high = mid - 1;
                    }
                    else
                    {
                        low = low + 1;
                    }
                }
            }
            return new int[] { -1, -1 };
        }

        //169.多数元素(哈希表、分治、投票(众数》0))
        //https://leetcode-cn.com/problems/majority-element/
        public int MajorityElement(int[] nums)
        {
            //Hashtable map = new Hashtable();
            //for (int i = 0; i < nums.Length; i++)
            //{
            //    if (!map.ContainsKey(nums))
            //    {
            //        map.Add(nums[i], 1);
            //    }
            //    else
            //    {
            //        int a = (int)map[nums[i]];
            //        map.Add(nums[i], a+1);
            //    }
            //}
            int condidate = nums[0];
            int count = 1;
            for (int i = 1; i < nums.Length; i++)
            {
                if (count == 0)
                {
                    count = 1;
                    condidate = nums[i];
                    continue;
                }
                if (condidate != nums[i])
                    count--;
                else
                    count++;
            }
            return condidate;
        }

        //179. 最大数
        //https://leetcode-cn.com/problems/largest-number/
        //
        public string LargestNumber(int[] nums)
        {
            var strs = nums.Select(x => x.ToString()).OrderByDescending(x => x, new LargestNumberComparer()).ToList(); //数组（对每一个元素字符化）.降序（相邻元素相加比较）.List列表
            string[] arr = strs.ToArray();
            var result = string.Join(null, arr).TrimStart('0'); //删除头部的0
            return result == "" ? "0" : result;
        }


        class LargestNumberComparer : IComparer<string>
        {
            public int Compare(string x, string y)
            {
                var a = x + y;
                var b = y + x;
                return a.CompareTo(b); //判断相加后结果
            }
        }


        //189. 旋转数组
        //https://leetcode-cn.com/problems/rotate-array/
        //方法：环装替换
        public void Rotate(int[] nums, int k)
        {
            k = k % nums.Length; //真正需要移动的次数
            int count = 0;  //元素移动的次数
            for (int start = 0; count < nums.Length; start++)  //for循环只是为了判断count当移动次数=数组值就结束，start就是初始赋值为0，不会变成1的
            {
                //初始化
                int curidx = start; //当前要移动值的下标
                int prev = nums[start]; //要移动的值
                do
                {
                    int nextIdx = (curidx + k) % nums.Length; //移动后的位置「要理解」
                    int tempv = nums[nextIdx];//定义一个中间变量存储被替换的值
                    nums[nextIdx] = prev; //替换值
                    //--------------- //上面完成了一个值的移动，下面准备下一个值移动的初始化
                    prev = tempv; //下一个要移动的值
                    curidx = nextIdx; //下一次要移动的下标
                    count++;//次数+1                 
                } while (start != curidx);
            }
        }

        //217 存在重复元素
        //https://leetcode-cn.com/problems/contains-duplicate/
        //方法：使用哈希表或者字典都可以
        public bool ContainsDuplicate(int[] nums)
        {
            HashSet<int> dic = new HashSet<int>();
            for (int i = 0; i < nums.Length; i++)
            {
                dic.Add(nums[i]);
            }
            return !(dic.Count == nums.Length);
        }

        //350 两个数组的交集 2
        //https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
        //有很多限制条件，看原文，使用Dictionary
        public int[] Intersect(int[] nums1, int[] nums2)
        {
            if (nums2.Length < nums1.Length)
                return Intersect(nums2, nums1); //优化
            Dictionary<int, int> dic = new Dictionary<int, int>(); //<元素，次数>
            List<int> result = new List<int>(nums1.Length); //存放交集
            foreach (var item in nums1)
            {
                if (dic.ContainsKey(item))
                {
                    dic[item]++; //次数加一
                }
                else
                {
                    dic[item] = 1;
                }
            }
            foreach (var item in nums2)
            {
                if (dic.ContainsKey(item) && dic[item] > 0)
                {
                    dic[item]--;
                    result.Add(item);
                }
            }
            return result.ToArray();
        }


        //283 移动零
        //https://leetcode-cn.com/problems/move-zeroes/
        //方法：不为0就往前移动
        public void MoveZeroes(int[] nums)
        {
            int curIdx = 0;
            for (int nextIdx = 0; nextIdx < nums.Length; nextIdx++)
            {
                if (nums[nextIdx] != 0)
                {   //i和j指向的值进行交换，两个数据进行交换
                    int temp = nums[curIdx];
                    nums[curIdx] = nums[nextIdx];
                    nums[nextIdx] = temp;
                    curIdx++;
                }
            }
        }


        //448. 找到所有数组中消失的数字
        //https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
        //思路：对应的数字放置在对应的 
        //思路2：hash
        public IList<int> FindDisappearedNumbers(int[] nums)
        {
            int n = nums.Length;
            for (int i = 0; i < nums.Length; i++)
            {
                int x = (nums[i] - 1) % n; //获取到原有的数值
                nums[x] += n; //对重复出现的+n
            }

            List<int> res = new List<int>();
            for (int i = 0; i < n; i++)
            {
                if (nums[i] <= n)
                {
                    res.Add(i + 1);
                }
            }
            return res;
        }

        //1 两数之和
        //https://leetcode-cn.com/problems/two-sum/
        //
        public int[] TwoSum1(int[] nums, int target)
        {
            Hashtable hashtable = new Hashtable(); //可以使用z
            //第一遍迭代将指定的键KEY和值VALUE存储到哈希表
            for (int i = 0; i < nums.Length; i++)
            {
                hashtable.Add(nums[i], i);
            }
            for (int i = 0; i < nums.Length; i++)
            {
                //complement这里充当的键Key
                int complement = target - nums[i];
                if (hashtable.ContainsKey(complement) && (int)hashtable[complement] != i) //是否存在这样的下标，且下标不能是自己
                {
                    //需要将object类型将至转换成int类型
                    return new int[] { i, (int)hashtable[complement] };
                }

            }
            throw new System.Exception("No Two Sum Resolution22222222");

        }



        //48 旋转图像
        //https://leetcode-cn.com/problems/rotate-image/
        //
        public void Rotate(int[][] matrix)
        {
            int pos1 = 0, pos2 = matrix.Length - 1;
            int cell = 0;
            while (pos1 < pos2)
            {
                cell = 0;
                while (cell < pos2 - pos1)
                {
                    int temp = matrix[pos2 - cell][pos1]; //左上
                    matrix[pos2 - cell][pos1] = matrix[pos2][pos2 - cell]; //左上=左下
                    matrix[pos2][pos2 - cell] = matrix[pos1 + cell][pos2]; //左下=右下
                    matrix[pos1 + cell][pos2] = matrix[pos1][pos1 + cell]; //右下=右上
                    matrix[pos1][pos1 + cell] = temp; //右上=左上

                    ++cell;
                }

                ++pos1;
                --pos2;
            }
        }


        //704. 二分查找
        //https://leetcode-cn.com/problems/binary-search/
        public int Search(int[] nums, int target)
        {
            int left = 0;
            int right = nums.Length - 1;
            while (left <= right)
            {
                int middle = left + (right - left) / 2; //防止溢出
                if (nums[middle] == target) return middle;
                if (target < nums[middle]) right = middle - 1; //右指针变换
                if (target > nums[middle]) left = middle + 1;
            }
            return -1;
        }


        public int SumDemo(int num)
        {
            int sum = 0;
            int temp = 1;
            for (int i = 1; i < num + 1; i++) //处理相加
            {
                for (int j = 1; j < i + 1; j++)
                {
                    temp = j * temp;
                }
                sum = temp + sum;
                temp = 1;
            }
            return sum;
        }


        //所需要的公共变量，并对其赋值~
        //需要挂载到一个游戏对象上
        public int num;
        public int[] nums;
        public int val;
        public int[] nums1;
        public int[] nums2;
        public int m;
        public int n;
        public int numRows;


        private void OnGUI()
        {
            if (GUI.Button(new Rect(30, 0, 100, 30), "测试"))
            {
                int result = SumDemo(num);
                Debug.Log(result);
            }


            if (GUI.Button(new Rect(30, 50, 120, 30), "26-删数组重复项"))
            {
                int result = RemoveDuplicates(nums);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(30, 100, 100, 30), "27-移除元素"))
            {
                int result = RemoveElement(nums, val);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(30, 150, 120, 30), "35-搜索插入位置"))
            {
                int result = SearchInsert(nums, val);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(30, 200, 100, 30), "53-最大子序和"))
            {
                int result = MaxSubArray(nums);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(30, 250, 100, 30), "66-加一"))
            {
                int[] result = PlusOne(nums);
                foreach (var item in result)
                {
                    Debug.Log(item);
                }
            }

            if (GUI.Button(new Rect(30, 300, 100, 30), "88-合并后排序"))
            {
                Merge(nums1, m, nums2, n);
            }

            if (GUI.Button(new Rect(30, 350, 100, 30), "118-动态规划"))
            {
                var list = Generate(numRows);
                foreach (var item in list)
                {
                    foreach (var a in item)
                    {
                        Debug.Log(a);
                    }
                }
            }

            if (GUI.Button(new Rect(30, 400, 100, 30), "119-层层覆盖"))
            {
                var list = GetRow(numRows);
                foreach (var item in list)
                {
                    Debug.Log(item);
                }
            }

            if (GUI.Button(new Rect(160, 50, 100, 30), "167-二分"))
            {
                var list = TwoSum(nums, val);
                foreach (var item in list)
                {
                    Debug.Log(item);
                }
            }

            if (GUI.Button(new Rect(160, 100, 100, 30), "169-投票众数"))
            {
                var result = MajorityElement(nums);
                Debug.Log(result);
                Object obj = new Object();
                if (!obj)
                {
                    Debug.Log("hhhhhh");
                }
            }

            if (GUI.Button(new Rect(160, 150, 100, 30), "122-股票2"))
            {
                var result = MaxProfit(nums);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(160, 200, 100, 30), "189-旋转数组"))
            {
                Rotate(nums, num);
                foreach (var item in nums)
                {
                    Debug.Log(item);
                }
            }


            if (GUI.Button(new Rect(160, 250, 120, 30), "217-存在重复元素"))
            {
                bool result = ContainsDuplicate(nums);
                Debug.Log(result);
            }


            if (GUI.Button(new Rect(160, 300, 120, 30), "136-只出现一次的数字"))
            {
                var result = SingleNumber(nums);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(160, 350, 120, 30), "350-两数组的交集2"))
            {
                var result = Intersect(nums1, nums2);
                foreach (var item in result)
                {
                    Debug.Log(item);
                }
            }

            if (GUI.Button(new Rect(160, 400, 120, 30), "283-移动0"))
            {
                MoveZeroes(nums);
                foreach (var item in nums)
                {
                    Debug.Log(item);
                }
            }

            if (GUI.Button(new Rect(290, 50, 120, 30), "1-两数之和1"))
            {
                var result = TwoSum1(nums, val);
                foreach (var item in result)
                {
                    Debug.Log(item);
                }
            }



        }

    }

    public delegate void DelegateTest();
    public interface ITest //只能包含非静态成员函数，隐式public，但不允许访问修饰符
    {
        void Method(string a); //方法
        string Property //属性
        {
            get; set;
        }
        event DelegateTest EventTest; //事件，需要先定义一个委托
        int this[int index] //索引器
        {
            get; set;
        }
    }
}
